package cn.initcap.algorithm.graph.util;

import cn.initcap.algorithm.graph.Edge;
import cn.initcap.algorithm.graph.Graph;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author initcap
 * @date Created in 2020/2/3 17:23.
 */
public class TopoSort<Weight extends Number & Comparable> {

    private Graph graph;

    private List<Integer> res;

    private boolean hasCycle = false;

    public TopoSort(Graph graph) {
        if (!graph.isDirected()) {
            throw new IllegalArgumentException("TopoSort only works in directed graph!");
        }
        this.graph = graph;
        this.res = new ArrayList<>();

        int[] indegrees = new int[graph.nodeSize()];
        // 存储入度值为0的
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < indegrees.length; i++) {
            indegrees[i] = graph.indegree(i);
            if (indegrees[i] == 0) {
                queue.add(i);
            }
        }

        while (!queue.isEmpty()) {
            int cur = queue.remove();
            res.add(cur);

            for (Object next : graph.adj(cur)) {
                Edge<Weight> edge = (Edge) next;
                indegrees[edge.w()]--;
                if (indegrees[edge.w()] == 0) {
                    queue.add(edge.w());
                }
            }
        }

        if (res.size() != graph.nodeSize()) {
            hasCycle = true;
            res.clear();
        }

    }

    public boolean isHasCycle() {
        return this.hasCycle;
    }

    public List<Integer> result() {
        return res;
    }
}
